Information on the Background of this invention can be found in U.S. Utility Pat. No. 8,868,332, METHOD AND SYSTEM FOR NAVIGATION USING BOUNDED GEOGRAPHIC REGIONS; and U.S. Pat. No. 8,775,059, METHOD AND SYSTEM FOR MULTI-VEHICLE, MULTI-DESTINATION ROUTING. This patent application will refrain from repeating the adequate Background described in its predecessor patents.
Navigation kernels which pre-existed the use of Bounded Geographic Regions (“BGRs”) had several performance deficiencies, namely inaccurate estimated time of arrival (“ETA”), and sub-optimum routing. A navigation kernel using BGRs can overcome many of these deficiencies, as described in the two above referenced patents.
However, the brute-force implementation of a navigation and guidance system using Bounded Geographic Regions (“BGRs”) is both labor-intensive and time-consuming. Specifically, the proper set-up of the BGRs with respect to a mapping database can be both labor-intensive and time-consuming. The relevant portions of a map database have to be partitioned into BGRs of roughly equal mean area, with an average, white, and Gaussian distribution about the mean. The BGRs need roughly equal aspect ratios, with any variance being average, white, and Gaussian about the mean. In practice, these first two requirements cause problems, because the curvature of the Earth causes variation of either the aspect ratio or the area.
Furthermore, an explicit solution is not necessarily guaranteed in attempting to simultaneously create BGRs over a very large region. This problem is caused because trying to overlay BGRs onto a large geographic region creates a very large number of degrees of freedom. Due to the large number of degrees of freedom, not all solutions converge on a set of acceptable BGRs. In other words, using a brute force method to try and overlay the Earth with BGRs can lead to repeated unacceptable solutions. Although a computer can be compiled with an adequate instruction set to keep searching until an acceptable solution is found, it can take a significant amount of time (days, weeks, or months, depending on the processing power employed).
The scale and scope of partitioning the Earth causes this problem, with BGRs of a reasonable area numbering easily into the millions or tens-of-millions. The problems can lead to either repeated unacceptable solutions, or to an inordinately long processing time. A set of techniques to minimize the burden of generating BGRs is needed.